package com.dbh.alg.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author dongbanghui
 * @date 2021/04/18
 */
public class QuickSort {

    /**
     * 快速排序
     * 对arr[l...r]部分进行排序
     * @param arr 排序数组
     * @param l 左边界
     * @param r 右边界
     */
    public void quick(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }
        int p = partition(arr, l, r);
        quick(arr, l, p-1);
        quick(arr, p+1, r);
    }

    /**
     * 对arr[l...r]部分进行partition操作，返回p使得arr[l...p-1] < arr[p];
     * arr[p+1...r] > arr[p]
     * @param arr 数组
     * @param l 左边界
     * @param r 有边界
     * @return partition值
     */
    private int partition(int[] arr, int l, int r) {
        //此处选取的是第一个元素为标定，可以随机在数组中选一个元素为标定
        int v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                int temp = arr[i];
                arr[i] = arr[j + 1];
                arr[j +1] = temp;
                j++;
            }
        }

        int temp = arr[l];
        arr[l] = arr[j];
        arr[j] = temp;
        return j;
    }


    /**
     * 二路快排（如果有大量重复元素，就会partition两个非常分不平衡的部分）
     * @param arr 排序元素
     * @param l 左边界
     * @param r 右边界
     */
    public void quick2(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }
        int p = partition2(arr, l, r);
        quick2(arr, l, p-1);
        quick2(arr, p+1, r);
    }

    /**
     * 对arr[l...r]部分机型partition操作
     * 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int partition2(int[] arr, int l, int r) {
        int v = arr[l];

        //arr[l+1...i] <= v; arr[j...r] >= v
        int i = l + 1, j = r;
        while(true) {
            while(i <= r && arr[i] < v) {
                i++;
            }
            while(j >= l + 1 && arr[j] > v) {
                j--;
            }
            if (i > j){
                break;
            }
            int temp= arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        int temp = arr[l];
        arr[l] = arr[j];
        arr[j] = temp;
        return j;
    }

    /**
     * 三路快排
     * @param arr
     * @param l
     * @param r
     */
    public void quick3(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }

        //partition
        int v = arr[l];
        //arr[l+1...lt] < v
        int lt = l;
        //arr[gt...r] > v
        int gt = r + 1;
        //arr[lt+1...i] == v
        int i = l + 1;
        while(i < gt) {
            if (arr[i] < v) {
                int temp = arr[i];
                arr[i] = arr[lt + 1];
                arr[lt + 1] = temp;
                lt++;
                i++;
            } else if (arr[i] > v){
                int temp = arr[i];
                arr[i] = arr[gt - 1];
                arr[gt - 1] = temp;
                gt--;
            } else {
                i++;
            }
        }
        int temp = arr[l];
        arr[l] = arr[lt];
        arr[lt] = temp;

        quick3(arr, l, lt-1);
        quick3(arr, gt, r);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] arr = {2,6,1,9,0,8,7,5,132,4,6,7,8,9,90,65,78,123,54,54,78,12,1,123,43,54,65,67};
        quickSort.quick3(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}
